package com.xufx.algorithm.sort;

/**
 * 归并排序
 * 1. 采用的是分治的思想（和快排是一样的）
 * 步骤：1 将数组分成不可再分的单位
 *      2 组合已经排序好的子数组
 *      3 拆分的时间不算在时间复杂度中（可以认为本来就已经拆好来）
 *      4 时间复杂度--> O(nlog(n))
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] nums = new int[]{4,3,2,1};
        mergeSort(nums);
        for (int num: nums) {
            System.out.println(num);
        }
    }

    private static int[] mergeSort(int[] nums){
        int len = nums.length;
        // 辅助数组
        int[] tmp = new int[len];
        doMergeSort(nums, 0, len - 1, tmp);
        return nums;
    }

    private static void doMergeSort(int[] nums, int left, int right, int[] tmp){
        if(left == right){
            return;
        }
        int mid = (left + right) / 2;
        doMergeSort(nums, 0, mid, tmp);
        doMergeSort(nums,mid + 1, right,tmp);
        // 合并两个子数组
        // 这个for循环的作用很简单，就是把nums 赋值给tmp
        for(int i = left; i <= right; i++){
            tmp[i] = nums[i];
        }
        int i = left;
        int j = mid + 1;
        // tmp数组分成了两部分，分别是left开头用i来做为游标
        //                       和mid+1开头用j来做为游标
        // 这里其实是用tmp数组的前后两个部分，来模拟两个数组（可以这样理解）
        // 也可以通过判断null的形式来做
        for(int k = left; k <= right; k++){
            // 如果只有右边的，直接赋值右边的部分
            if(i == mid + 1) {
                nums[k] = tmp[j];
                j++;
            }
            // 如果只有左边的，直接赋值左边的部分
            else if (j == right + 1){
                nums[k] = tmp[i];
                i++;
            }
            // 比大小，哪个小哪个在前面
            else if(tmp[i] <= tmp[j]){
                nums[k] = tmp[i];
                i++;
            }else{
                nums[k] = tmp[j];
                j++;
            }
        }
    }
}
